//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    //dp[i][j] 表示word1前i个字符转换成word2前j个字符花最少操作数【即编辑距离】
    //word1[i]!=word2[j]
    //插入：r 1+dp[i][j-1]   //删除dp[i-1][j]+1  //替换dp[i-1][j-1]+1
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        if (m * n == 0)return m + n;
        int dp[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    int insertNum = 1 + dp[i][j - 1];
                    int deleteNum = 1 + dp[i - 1][j];
                    int replaceNum = 1 + dp[i - 1][j - 1];
                    dp[i][j] = min(insertNum, min(deleteNum, replaceNum));
                }
            }
        }
        return dp[m][n];
    }

    }
};